// 给定一个字符串 s，将 s 分割成一些子串，使每个子串都是回文串。
// 思路，回溯
// 其实就是s的不同分割方案的组合
function partition(s) {
    if (!s.length) {
        return []
    }
    let result = []
    let path = []
    function backtracking(startIndex) {
        if (startIndex >= s.length) {
            result.push([...path])
            return
        }
        for (let i = startIndex; i < s.length; i++) {
            if (isPalindrome(s, startIndex, i)) {
                path.push(s.substring(startIndex, i + 1))
                backtracking(i + 1)
                path.pop()
            }
        }
    }
    backtracking(0)
    return result
}

function isPalindrome(s, left, right) {
    while (left < right) {
        if (s[left] !== s[right]) {
            return false
        }
        left++
        right--
    }
    return true
}

console.log(partition('aabb'))

// 思路2，利用dp记录字符串子串是否是回文字符串
function partition2(s) {
    if (!s.length) {
        return []
    }
    let dp = new Array(s.length).fill(0).map(_ => new Array(s.length).fill(false))
    function createDp() {
        for (let i = s.length - 1; i >= 0; i--) {
            for (let j = i; j < s.length; j++) {
                if (i === j) {
                    dp[i][j] = true
                } else if (j - i === 1) {
                    dp[i][j] = s[i] === s[j]
                } else {
                    dp[i][j] = s[i] === s[j] && dp[i+1][j-1]
                }
            }
        }
    }
    createDp()
    let result = []
    let path = []
    function backtracking(startIndex) {
        if (startIndex >= s.length) {
            result.push([...path])
            return
        }
        for (let i = startIndex; i < s.length; i++) {
            if (dp[startIndex][i]) {
                path.push(s.substring(startIndex, i + 1))
                backtracking(i + 1)
                path.pop()
            }
        }
    }
    backtracking(0)
    return result
}

console.log(partition2('aab'))